package baseclass.m_graph;

import java.util.*;

/**
 * 拓扑排序是生活中非常常见的一种。比如java微服务项目中，各个项目相互依赖，
 * 最后打包的过程中，
 * 若要打包A，则必须把A所依赖的都先于A打包好。这就是拓扑排序。
 *
 * 算法：找出入度为0的边，然后剔除该边，更新所有节点的入度。依次遍历，将入度为0的重复以上操作。
 * 注意，该算法前提肯定不能形成环。
 *
 * A←B←C←D←E←F   先做F，再做E，...最后做A
 * @date 2020/3/6 21:35
 */
public class Code03_TuoPuSort {
    public static List<Node> tuopuSort(Graph graph){
        if(graph == null) return new LinkedList<>();
        //统计节点的入度
        Map<Node,Integer> map = new HashMap<>();
        //队列，按照入度为0优先排列，也是拓扑的顺序
        Queue<Node> zeroQueue = new LinkedList<>();
        //
        List<Node> res = new LinkedList<>();
        //graph.nodes是HashMap，K是编号，V是节点
        for (Node node : graph.nodes.values()) {
            map.put(node,node.in);
            if(node.in == 0) zeroQueue.offer(node);
        }
        while (!zeroQueue.isEmpty()){
            //这个是出队，按照顺序拓扑排序
            Node node = zeroQueue.poll();
            res.add(node);
            //更新node的所有邻居的入度
            for (Node next : node.nexts) {
                map.put(next,map.get(next)-1);
                if(map.get(next)== 0) zeroQueue.offer(next);
            }

        }
        return res;
    }
    public static void main(String[] args) {
        Integer[][]matrix =
                {{1,2,1}, {1,3,1}, {1,4,1}, {1,3,2}, {1,5,2}, {1,5,4}};
        Graph graph = Graph.createGraph(matrix);
        List<Node> list = tuopuSort(graph);
        for (Node node : list) {
            System.out.print(node.val+" - >");
        }
    }

}
